#include <unordered_set>
#include<vector>
#include <string>
using namespace std;
class Solution
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        unordered_set<string> word_set;
        for (auto &e : wordDict)
            word_set.insert(e);
        vector<bool> dp(s.size(), false);
        if (word_set.count(s.substr(0, 1)))
            dp[0] = 1;
        for (int i = 1; i < s.size(); i++)
            for (int j = i - 1; j >= -1; j--)
                if ((j >= 0 && dp[j] || j < 0) && word_set.count(s.substr(j + 1, i - j)))
                    dp[i] = true;
        return dp.back();
    }
};